package BT_39;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
	

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		int len = candidates.length;
		Arrays.sort(candidates);
		List<Integer> temp= new LinkedList<Integer>();
		BT(candidates,len,target,0,temp,res);
		return res;
				
	}

	

	private void BT(int[] candidates, int len, int target, int place, List<Integer> temp, List<List<Integer>> res) {
		// TODO Auto-generated method stub
		if (target==0) {
			res.add(new LinkedList<Integer>(temp));
			return ;
		}
		for (int i = place; i < len; i++) {
			if (target<candidates[i]) {
				break;
			}
			
			temp.add(candidates[i]);
			BT(candidates, len, target-candidates[i], i, temp, res);
			temp.remove(temp.size()-1);
		}
	}
}
